Posters - Schedules

Despite advances in method development for multiple sequence alignment over the last several decades, the alignment of datasets exhibiting substantial sequence length heterogeneity, especially when the input sequences include very short sequences (either as a result of sequencing technologies or of large deletions during evolution) remains an inadequately solved problem. We present HMMerge, a method to compute an alignment of datasets exhibiting high sequence length heterogeneity, or to add short sequences into a given "backbone" alignment. HMMerge builds on the technique from its predecessor alignment methods, UPP and WITCH, which build an ensemble of HMMs for the backbone alignment and add the remaining sequences into the backbone alignment using the ensemble. HMMerge differs from UPP and WITCH by building a new HMM for each query sequence: it uses a novel ensemble approach to combine the HMMs, each weighted by the probability of generating the query sequence, into a single HMM. Then it applies the Viterbi algorithm to add the query sequence into the backbone alignment. We show that using this "merged" HMM provides better accuracy than the current approach in UPP and matches or improves on WITCH for adding short sequences into backbone alignments. HMMerge is freely available at https://github.com/MinhyukPark/HMMerge. Supplementary materials are available at https://doi.org/10.1101/2022.05.29.493880.

Phylogenetic placement is the problem of placing “query” sequences into an existing tree (called a “backbone tree”), and is useful in both microbiome analysis and to update large evolutionary trees. The most accurate phylogenetic placement method to date is the maximum likelihood-based method pplacer, which uses RAxML to estimate numeric parameters on the backbone tree and then adds the query sequence to the edge that maximizes the probability that the resulting tree generates the query sequence. Unfortunately, pplacer fails to return valid outputs on many moderately large datasets, and so is limited to backbone trees with at most 10,000 leaves. We present a technique enabling pplacer to scale to large backbone trees. We draw on two prior approaches: the divide-and-conquer strategy in SCAMPP (Wedell et al., TCBB 2022) and the use of FastTree2 (Price et al., PLOS One 2010) instead of RAxML to estimate numeric parameters. We find that pplacer-SCAMPP-FastTree matches or improves the accuracy of other placement methods, can scale to large backbone trees with 200,000 sequences, and does so quickly with moderate memory usage. Additionally, pplacer-SCAMPP-FastTree enables the user to explore the runtime-accuracy trade-off by varying the placement tree size. Availability: https://github.com/gillichu/PLUSplacer-taxtastic. Paper and supplement: https://www.biorxiv.org/content/10.1101/2022.05.23.493012v1.